The present invention relates to content addressable memory (CAM) arrays. More specifically, the present invention relates to CAM arrays including ternary CAM cells.
Semiconductor memory devices fall into two broad categories: read only memory (ROM) devices, and read-write or xe2x80x9crandom accessxe2x80x9d memory (RAM) devices. ROM (e.g., EPROM or EEPROM) devices are non-volatile devices primarily used to store data when system power is turned off. In contrast, RAM devices temporarily store data that is used during system operation. RAM devices are typically volatile in that the data stored in a RAM device is lost when power is turned off. RAM devices are roughly divided into two types: static random access memory (SRAM) devices, and dynamic random access memory (DRAM) devices.
An SRAM device consists of a basic bistable flipflop circuit that needs only an applied DC current to retain a data value. To store a logic xe2x80x9c1xe2x80x9d data value (bit), the bistable flipflop is biased into a first stable state, and to store a logic xe2x80x9c0xe2x80x9d data value, the bistable flipflop is biased into its second stable state. The bistable flipflop maintains the first or second stable state until an opposite biasing voltage is applied that xe2x80x9cflipsxe2x80x9d the bistable flipflop from the first to the second (or the second to the first) stable state. While the stable data storage of SPAM devices provides certain advantages, a main disadvantage of SRAM devices is their relatively large size due to the multiple (typically six or more) transistors required to form and access the bistable flipflop circuit.
In contrast to SRAM devices, DRAM devices stores a data value as a charge on a capacitor or wire (referred to herein as a xe2x80x9cstorage nodexe2x80x9d). The main advantage of DRAM devices is that a basic DRAM memory cell requires only a single transistor and a capacitor (or wire), thereby making DRAM cells significantly smaller and less expensive to produce than SRAM cells. The main disadvantage of DRAM devices is that the data values stored in the storage node decay over time, thereby requiring refresh circuitry that periodically reads and rewrites (refreshes) the stored data values to prevent their loss. Due to the sensitivity typical of DRAM devices, this refresh operation must be performed independent of other (e.g., read or write) operations. In particular, the data value (voltage) stored in the storage node of a DRAM memory cell is read using a sense amplifier during a read phase of the refresh operation, and then the sense amplifier refreshes (rewrites) the sensed data value during a write phase of the refresh operation. Due to the read phase of the refresh operation, the number of memory cells in each column of a DRAM array must be minimized. That is, the length (i.e., capacitance) of bit lines increases with the number of DRAM memory cells arranged in a column that are connected to these lines. Because the data values are partially decayed before being transmitted from each DRAM memory cell onto bit lines, this capacitance can generate read phase errors if the bit lines are too long. In particular, this sensitivity restricts the use of DRAM devices in the direct control a logic gate or the gate terminal of a pass transistor in an integrated circuit.
Conventional RAM arrays include RAM cells arranged in rows and columns, and addressing circuitry that accesses a selected row of RAM cells using address data corresponding to the physical address of the RAM cells. That is, data words stored in the rows of conventional RAM cells are accessed by applying address signals to the RAM array input terminals. In response to each unique set of address signals, a RAM array outputs a data word that is read from a group of RAM cells designated by the address.
Unlike conventional RAM arrays, content addressable memory (CAM) arrays include CAM cells that are addressed in response to their content, rather than by a physical address within a RAM array. Specifically, a CAM array receives a data word that is compared with all of the data values stored in the CAM cells located in each row of the CAM array. In response to each unique data word applied to the CAM array input terminals, the rows of CAM cells within the CAM array assert or de-assert associated match signals indicating whether or not all of the data values stored in the CAM cells of a row match the applied data word. CAM arrays are useful in many applications, such as search engines.
Similar to conventional RAM devices, CAM cells can either be formed as DRAM devices, in which data values are stored in storage nodes formed by capacitors or wires, or SRAM devices, in which data values are stored using bistable flipflop circuits. Similar to conventional RAM cells, DRAM CAM cells provide an advantage in that they are typically smaller than SRAM CAM cells, but require a refresh operation that can impede high speed match operations. In addition, DRAM CAM arrays are typically limited in size due to the capacitance problems, discussed above, that are associated with DRAM memory cells. In contrast, SRAM memory cells typically require more transistors (and, hence, more substrate area) than DRAM cells, but avoid the capacitance problems associated with DRAM CAM cells.
CAM cells are typically defined by the number of data values that they store. For example, binary CAM cells stores one of two logic values: a logic high value or a logic low value. Ternary CAM cells store one of three logic values: a logic high value, a logic low value, and a xe2x80x9cdon""t carexe2x80x9d logic value. A xe2x80x9cdon""t carexe2x80x9d logic value is a logic value that produces a match condition for any applied compare data value. When the logic value stored in a ternary CAM cell matches an applied data value, assuming all other CAM cells coupled to the CAM array row also match, then the voltage on the match line coupled to the ternary CAM cell is maintained at the match value (e.g., a logic high value), thereby indicating that a match has occurred. In contrast, when the logic value stored in the ternary CAM cell does not match an applied data value, then the voltage on the match line coupled to the ternary CAM cell is changed to the no match value (e.g., pulled down to a logic low value), thereby indicating that a match has not occurred. A ternary CAM cell storing a xe2x80x9cdon""t carexe2x80x9d value will provide a match condition for any data value applied to that CAM cell. This xe2x80x9cdon""t carexe2x80x9d capability allows CAM arrays to indicate when a data value matches a selected group of ternary CAM cells in a row of the CAM array.
Higher order CAM cells store additional data values. For example, a four state (xe2x80x9cquadxe2x80x9d CAM cell stores a logic high value, a logic low value, a logic high xe2x80x9cdon""t carexe2x80x9d value, and a logic low xe2x80x9cdon""t carexe2x80x9d value. Thus, a CAM cell storing four states beneficially stores a data value (e.g., a high or low value) and simultaneously indicates whether that data value is to be involved in a match operation (e.g., a logic high or a logic high xe2x80x9cdon""t carexe2x80x9d). As a result, a read operation on a four-state CAM cell storing a xe2x80x9cdon""t carexe2x80x9d value distinguishes the xe2x80x9cdon""t carexe2x80x9d value read from the CAM cell as either a logic high xe2x80x9cdon""t carexe2x80x9d value or a logic low xe2x80x9cdon""t carexe2x80x9d value. Match operations performed by a four-state CAM cell are similar to the ternary CAM cell described above.
FIG. 10 is a schematic diagram of a conventional ternary CAM cell 1000. CAM cell 1000 is a sixteen-transistor (16-T) device including two 6-transistor (6-T) SRAM cells 1001A and 1001B and a 4-T exclusive-NOR (comparator) circuit 1001C. SRAM cell 1001A includes n-channel transistors 1010, 1011, 1014, and 1015 and p-channel transistors 1022 and 1023. Transistors 1014, 1015, 1022, and 1023 are cross-coupled to form a storage latch having storage node N1 and inverted storage node N1#. Access transistors 1010 and 1011 couple storage node N1# and N1, respectively, to inverted bit line B1# and bit line B1, respectively. Similarly, SRAM cell 1001B includes n-channel transistors 1016 and 1017 and p-channel transistors 1024 and 1025, which are cross-coupled to form a storage latch having node N2 and inverted storage node N2#, and access transistors 1012 and 1013, which couple storage nodes N2# and N2, respectively, to inverted bit line B2# and bit line B2, respectively. Exclusive NOR circuit 1001C includes n-channel transistors 1018-1021. Transistors 1020 and 1018 are coupled in series between a match line MATCH1 and a steady state supply source (i.e., Vss or ground). The gate terminal of transistor 1020 is coupled to node N1 and the gate of transistor 1018 is coupled to an inverted data line D1#. Similarly, transistors 1021 and 1019 are coupled in series between the match line and the steady state supply source. The gate of transistor 1021 is coupled to node N2# and the gate of transistor 1019 is coupled to a data line D1.
Ternary CAM cell 1000 stores one of a logic high, a logic low, and a logic xe2x80x9cdon""t carexe2x80x9d value by selectively storing data values in nodes N1 and N2, and inverted data values in nodes N1# and N2#, during a write operation. During subsequent read operations, the values stored in nodes N1, N2, N1# and N2# are provided on bit lines B1 and B2 and inverted bit lines B1# and B2#, respectively. During a compare operation, the value stored in node N2# is compared to a data value and the value stored in node N1 is compared to an inverted data value. Depending upon the outcome of this comparison, match line MATCH1 is either maintained in a charged state (indicating a match condition) or discharged to ground (indicating a no-match condition) in response to the applied data and inverted data values. As used herein, the term xe2x80x9cdischargedxe2x80x9d means a voltage state is changed. Thus, in one embodiment, xe2x80x9cdischargedxe2x80x9d may mean a logic high value of a match line is discharged to a logic low value or ground. In another embodiment, xe2x80x9cdischargedxe2x80x9d may mean a logic low value of a match line is discharged to a logic high value or the Vcc voltage supply source.
A problem with conventional ternary CAM cell 1000 is that the 16 transistors forming ternary CAM cell 1000 take up valuable chip area. It is preferred to minimize the number of transistors required to perform a function to maximize available chip area. Another problem with conventional ternary CAM cell 1000 is the space required by the six bit lines (i.e., B1, B1#, B2, B2#, D1A, and D1B#) that are required to write data values to ternary CAM cell 1000. These many bit lines and associated connections similarly occupy valuable chip area. It would therefore be desirable to have a CAM cell having a minimized area that is capable of storing at least three values.
U.S. Pat. No. 5,841,874 discloses a 14-T ternary CAM cell including two 5-T memory cells and a 4-T comparator circuit. Although the size of this 14-T ternary CAM cell is smaller than that of ternary CAM cell 1000 (shown in FIG. 10), the 14-T ternary CAM cell requires a much more difficult read and write operations because the 5-T memory cells must be read and written separately via the comparator circuit.
What is needed is a ternary CAM cell having a minimum cell size that combines the stable operation of SRAM devices with the space saving benefits of DRAM devices, and avoids the complicated write and read operations associated with conventional reduced-size ternary SRAM CAM cells.
The present invention is directed to a reduced size ternary CAM cell including a binary SRAM CAM cell connected in series with a mask transistor to form a discharge path between a match line and a discharge line, and a DRAM mask circuit that applies a mask (i.e., care/don""t care) value to the gate terminal of the mask transistor. The binary SRAM CAM cell includes a single latch for storing a data value that is compared with applied data values during match operations, and the DRAM mask circuit includes two DRAM memory cells that cooperatively store and continuously apply the mask value to the gate terminal of the mask transistor. By combining a binary SRAM CAM cell and mask transistor with the DRAM mask circuit in accordance with the present invention, a ternary CAM cell is provided that combines the performance benefits of an SRAM CAM cell while using fewer transistors (and, hence, having a smaller size) than conventional ternary SRAM CAM cells.
During match operations, the binary SRAM CAM cell compares applied data values with a stored data value, and opens a portion of the discharge path when the applied data value fails to match the stored data value. The mask transistor is provided to perform the care/don""t care function in accordance with the mask value stored in the DRAM mask circuit, thereby facilitating ternary CAM operations. When the mask value is logic xe2x80x9c0xe2x80x9d (i.e., low or xe2x80x9cdon""t carexe2x80x9d), the mask transistor is held open (turned off) such that the match line is unable to discharge even when a data value stored in the binary CAM cell fails to match an applied data value. Conversely, when the mask value is logic xe2x80x9c1xe2x80x9d (i.e., high or xe2x80x9ccarexe2x80x9d), the mask transistor is continuously closed (turned on) such that, consistent with conventional binary CAM cells, the match line discharges to the discharge line when a data value stored in the binary CAM cell fails to match an applied data value.
In accordance with an aspect of the present invention, the DRAM mask circuit of each ternary CAM cell includes a first DRAM memory cell and a second DRAM memory cell that are connected to a single bit line (central node), and a storage node of the second DRAM memory cell is connected to the gate terminal of the mask transistor. Because the first and second DRAM memory cells are connected to a single bit line (central node), the first DRAM memory cell is able to refresh the second DRAM memory cell without requiring the mask value to be read from the second DRAM memory cell. Specifically, during a read phase of a refresh operation, a first word line signal is transmitted to the first DRAM memory cell to write a mask value from the storage node of the first DRAM memory cell to the bit line. A sense amplifier connected to the bit line then reads and amplifies (refreshes) the mask value transmitted on the bit line from the first DRAM memory cell. During the subsequent write phase of the refresh operation, a second word line signal is transmitted to the second DRAM memory cell, thereby writing the refreshed mask value from the bit line to the second DRAM memory cell. Accordingly, the mask value stored in the second DRAM memory cell and applied to the mask transistor is refreshed without reading the mask value from the second DRAM memory cell, thereby avoiding the problems associated with conventional single DRAM memory cell control circuits.
In accordance with another aspect of the present invention, a CAM circuit includes an array of ternary CAM cells that are accessed by associated control circuits. Data values are written to and read from each binary SRAM CAM cell using first word and bit lines, and mask values are written to and read from each DRAM mask circuit using separate word and bit lines. With this arrangement, both the data value and the mask (care/don""t care) value can be written and read simultaneously during read and write operations, respectively, thereby avoiding the difficult read and write operations required by some conventional ternary SRAM CAM cells.
In a first disclosed embodiment of the present invention, a 9-T ternary CAM cell is produced by using a 6-T binary CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor and to the match line by a second pass transistor. One of the transistors that forms the latch and is controlled by the data value stored in the latch is connected in series with the mask transistor and the second pass transistor, which is controlled by the applied data value, to form the discharge path between the match line and a discharge line. The resulting structure provides a highly space efficient ternary CAM cell.
In a second disclosed embodiment, a 10-T ternary CAM cell includes a 7-T binary SRAM CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor, to an inverted bit line by a second transistor, and to the mask transistor by a third pass transistor controlled by the applied data value. Similar to the first disclosed embodiment, one of the transistors that forms the latch is connected in series with the mask transistor and the third pass transistor to form the discharge path between the match line and a discharge line. However, in the second disclosed embodiment, the mask transistor is connected between a first terminal of the third pass transistor and the match line, and the latch is connected to ground/VSS. Because the latch is directly connected to ground/VSS, the second pass transistor and inverted bit line are provided to reliably write data values to (i.e., xe2x80x9cflipxe2x80x9d) the latch of the binary SRAM CAM cell.
In a third disclosed embodiment, a 11-T ternary CAM cell includes an 8-T binary SRAM CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor, and to the mask transistor by a second pass transistor and a third pass transistor that are connected to opposite nodes, respectively, of the latch and are controlled by the applied data value and its inverse, respectively. The binary SRAM CAM cell also includes a pull-down transistor that is connected to a node located between the mask transistor and the third and fourth pass transistors. A first branch of the discharge path is formed by a first transistor of the latch that is connected in series with the mask transistor and the second pass transistor. A second branch of the discharge path is formed by a second transistor of the latch that is connected in series with the mask transistor and the third pass transistor. During write operations, the first pass transistor and the pull-down transistor are turned on, and one of the second and third pass transistors is turned on to store a desired data value in the latch. During match operations, one of the first and second branches of the discharge path are opened when the applied data value (or its inverse) fail to match the data value (or its inverse) that is stored in the latch.
In a fourth disclosed embodiment, another 11-T ternary CAM cell includes an 8-T binary SRAM CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor, to an inverted bit line by a second pass transistor, and to the mask transistor by a third pass transistor and a fourth pass transistor that are connected to opposite nodes, respectively, of the latch and are controlled by the applied data value and its inverse, respectively. A first branch of the discharge path is formed by a first transistor of the latch that is connected in series with the mask transistor and the third pass transistor. A second branch of the discharge path is formed by a second transistor of the latch that is connected in series with the mask transistor and the fourth pass transistor. During write operations, the first and second pass transistors are turned on to store a desired data value in the latch from the bit line and the inverted bit line. During match operations, one of the first and second branches of the discharge path are opened when the applied data value (or its inverse) fail to match the data value (or its inverse) that is stored in the latch.
In a fifth disclosed embodiment, a 13-T ternary CAM cell includes a 10-T binary SRAM CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor, and to an inverted bit line by a second pass transistor. A first node of the latch is connected to the gate terminal of a third pass transistor, which is connected in series with a fourth pass transistor and the mask transistor to form a first branch of the discharge path between the match line and the discharge line. A second node of the latch is connected to the gate terminal of a fifth pass transistor, which is connected in series with a sixth pass transistor and the mask transistor to form a second branch of the discharge path between the match line and the discharge line. The fourth and sixth pass transistors are controlled by the applied data value and its inverse, respectively. The discharge line is maintained in a floating state during read, write, and standby operations to conserve power. During match operations, one of the first and second branches of the discharge path are opened when the applied data value (or its inverse) fail to match the data value (or its inverse) that is stored in the latch.
In a sixth disclosed embodiment, a 12-T ternary CAM cell includes a 9-T binary SRAM CAM cell, a 2-T mask circuit, and the mask transistor. The binary SRAM CAM cell includes a 4-T latch that is connected to a bit line by a first pass transistor, and to an inverted bit line by a second pass transistor. A first node of the latch is connected to the gate terminal of a third pass transistor, and a second node of the latch is connected to the gate terminal of a fourth pass transistor. The third and fourth pass transistors are connected to a gate terminal of a fifth pass transistor, which is connected in series with the mask transistor to form the discharge path between the match line and the discharge line.
The present invention will be more fully understood in view of the following description and drawings.